package com.test.sort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort extends BaseSort{

    public static void main(String[] args) {
        //1纳秒=0.000001 毫秒=10的负6次方毫秒
        //一秒的10亿分之一，即等于10的负9次方秒。常用作 内存读写速度的单位
        long start = System.nanoTime();
        BaseSort sort = new InsertSort();
        int[] a = {8, 2, 1, 6, 3, 9, 5, 7, 23, 13};
        sort.sort(a);
        long end = System.nanoTime();
        System.err.println((end-start)+"纳秒");
        Arrays.stream(a).forEach(System.out::println);

    }

    /**
     * 插入排序
     * 1从第一个元素开始，该元素可以认为已经被排序；
     * 2取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
     * 3如果该元素（已排序）大于新元素，将该元素移到下一位置；
     * 4重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
     * 5将新元素插入到该位置后；
     * 6重复步骤3~5
     *
     * 平均时间复杂度：O(n²)  因为使用了for+while循环
     * 空间复杂度：O(1)
     * 算法稳定性：稳定
     *
     * @param nums
     */
    @Override
    protected void sort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            //当前值
            int curr = nums[i + 1];
            //上一个数的指针
            int preIndex = i;
            //在数组中找到一个比当前遍历的数小的第一个数
            while (preIndex >= 0 && curr < nums[preIndex]) {
                //把比当前遍历的数大的数字往后移动
                nums[preIndex + 1] = nums[preIndex];
                //需要插入的数的下标往前移动
                preIndex--;
            }
            //插入到这个数的后面
            nums[preIndex + 1] = curr;
        }
    }
}
